{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Subarrays Having Even Product"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #math #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #数学 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: evenProduct"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #乘积为偶数的子数组数"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个整数数组 <code>nums</code>，返回<em>具有偶数乘积的 </em><code>nums</code><em> 子数组的数目</em>。</p>\n",
    "\n",
    "<p><strong>子数组&nbsp;</strong>是数组中连续的非空元素序列。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [9,6,7,13]\n",
    "<strong>输出:</strong> 6\n",
    "<strong>解释:</strong> 有6个子数组的乘积是偶数:\n",
    "- nums[0..1] = 9 * 6 = 54.\n",
    "- nums[0..2] = 9 * 6 * 7 = 378.\n",
    "- nums[0..3] = 9 * 6 * 7 * 13 = 4914.\n",
    "- nums[1..1] = 6.\n",
    "- nums[1..2] = 6 * 7 = 42.\n",
    "- nums[1..3] = 6 * 7 * 13 = 546.\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> nums = [7,3,5]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong> 没有乘积是偶数的子数组\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-subarrays-having-even-product](https://leetcode.cn/problems/number-of-subarrays-having-even-product/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-subarrays-having-even-product](https://leetcode.cn/problems/number-of-subarrays-having-even-product/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[9,6,7,13]', '[7,3,5]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    # # dp 枚举\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        ans, lst, n = 0, -1, len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i] & 1:\n",
    "                lst = i\n",
    "\n",
    "            ans += lst + 1\n",
    "\n",
    "        return ans  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        ans, lst, n = 0, -1, len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i] & 1:\n",
    "                lst = i\n",
    "\n",
    "            ans += lst + 1\n",
    "\n",
    "        return ans  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        #因为无后效性,考虑DP\n",
    "        #空间优化\n",
    "        n=len(nums)\n",
    "        if nums[0]&1:\n",
    "            odd,even=1,0\n",
    "        else:\n",
    "            odd,even=0,1\n",
    "        ans=even\n",
    "        for i in range(1,n):\n",
    "            if nums[i]&1==0:\n",
    "                even,odd=odd+even+1,0\n",
    "            else:\n",
    "                even,odd=even,odd+1\n",
    "            ans+=even\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        res = 0\n",
    "        last = -1\n",
    "        n = len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i] & 1:\n",
    "                last = i\n",
    "            res += last + 1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        n, j = len(nums), -1\n",
    "        return sum(not nums[i] & 1 and (n - i) * (-j + (j := i)) for i in range(n))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        #因为无后效性,考虑DP\n",
    "        #空间优化\n",
    "        n=len(nums)\n",
    "        if nums[0]&1:\n",
    "            odd,even=1,0\n",
    "        else:\n",
    "            odd,even=0,1\n",
    "        ans=even\n",
    "        for i in range(1,n):\n",
    "            if nums[i]&1==0:\n",
    "                even,odd=odd+even+1,0\n",
    "            else:\n",
    "                even,odd=even,odd+1\n",
    "            ans+=even\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        ans, lst, n = 0, -1, len(nums)\n",
    "        for i in range(n):\n",
    "            if not (nums[i] & 1):\n",
    "                lst = i\n",
    "\n",
    "            ans += lst + 1\n",
    "\n",
    "        return ans  \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        result, n, j = 0, len(nums), -1\n",
    "        for i in range(n):\n",
    "            if not nums[i] & 1:\n",
    "                result += (i - j) * (n - i)\n",
    "                j = i\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        #因为无后效性,考虑DP\n",
    "        #空间优化\n",
    "        n=len(nums)\n",
    "        if nums[0]&1:\n",
    "            odd,even=1,0\n",
    "        else:\n",
    "            odd,even=0,1\n",
    "        ans=even\n",
    "        for i in range(1,n):\n",
    "            if nums[i]&1==0:\n",
    "                even,odd=odd+even+1,0\n",
    "            else:\n",
    "                even,odd=even,odd+1\n",
    "            ans+=even\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        ans,lst,n = 0,-1,len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i] & 1:\n",
    "                lst = i\n",
    "            ans += lst + 1\n",
    "        return ans\n",
    "        \n",
    "    def evenProduct2(self, nums: List[int]) -> int:\n",
    "        # 定义状态表示数组dp, 其中的元素为一个二元组\n",
    "        # dp[i][0]表示以nums[i]结尾的乘积为偶数的数组数量\n",
    "        # dp[i][1]表示以nums[i]结尾的乘积为奇数的数组数量\n",
    "        # 若当前nums[i]为奇数，则可以与nums[i - 1]结尾的乘积为偶数的数组组合\n",
    "        # 所以dp[i][0] = dp[i - 1][0], dp[i][1] = dp[i - 1] + 1(可以和nums[i - 1]结尾的组合成乘积为奇数的数组，包括自己)\n",
    "        \n",
    "        # nums[i]为偶数时, 则可以和以nums[i - 1]结尾的任何数组组合为乘积为偶数的数组\n",
    "        # dp[i][0] = i + 1 (包括自己)\n",
    "        # 无法组合成乘积为奇数的数组 dp[i][1] = 0\n",
    "\n",
    "        # 每个dp[i]都只依赖与dp[i - 1]，所以可以使用滚动数组优化\n",
    "        a = b = ans = 0\n",
    "        for i, n in enumerate(nums, start = 1):\n",
    "            if n & 1:\n",
    "                b += 1\n",
    "            else:\n",
    "                a = i\n",
    "                b = 0\n",
    "            ans += a\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        ans=0\n",
    "        last=-1\n",
    "        n=len(nums)\n",
    "        for i in range(n):\n",
    "            if not nums[i]&1:\n",
    "                last=i\n",
    "            ans+=last+1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        pre, cnt = -1, 0\n",
    "        n = len(nums)\n",
    "        for idx, x in enumerate(nums):\n",
    "            if x & 1: continue\n",
    "            cnt += (idx - pre) * (n - idx)\n",
    "            pre = idx\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        pre = 0\n",
    "        res = 0\n",
    "        for i,val in enumerate(nums):\n",
    "            if val % 2 == 0:\n",
    "                pre = i+1\n",
    "            res += pre\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        i = 0\n",
    "        cnt = 0\n",
    "        while i < n:\n",
    "            if nums[i] & 1:\n",
    "                j = i\n",
    "                k = 0\n",
    "                while j < n and nums[j] % 2:\n",
    "                    j += 1\n",
    "                    k += 1\n",
    "                i = j\n",
    "                cnt += k * (k + 1) // 2\n",
    "            else:\n",
    "                i += 1\n",
    "        return n * (n + 1) // 2 - cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        n = len(nums)\n",
    "        nums = [-1] + [i for i, x in enumerate(nums) if x % 2 == 0] + [n]\n",
    "        tot = 0\n",
    "        for x, y in pairwise(nums):\n",
    "            tot += (y-x) * (y-x-1) // 2\n",
    "\n",
    "        return n * (n+1) // 2 - tot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def evenProduct(self, nums: List[int]) -> int:\n",
    "        #因为无后效性,考虑DP\n",
    "        n=len(nums)\n",
    "        dp=[0]*n\n",
    "        op=[0]*n\n",
    "        if nums[0]&1:\n",
    "            dp[0]=1\n",
    "        else:\n",
    "            op[0]=1\n",
    "        ans=op[0]\n",
    "        for i in range(1,n):\n",
    "            if nums[i]&1==0:\n",
    "                op[i]=dp[i-1]+op[i-1]+1\n",
    "                dp[i]=0\n",
    "            else:\n",
    "                op[i]=op[i-1]\n",
    "                dp[i]=dp[i-1]+1\n",
    "            ans+=op[i]\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
